package com.youkeda.excise;

import java.util.Arrays;

/**
 * @author CoderXshuai
 * @date 2020/7/16/0016 11:23
 */

public class Sort {
    // 快速选择，返回选中的元素
    public static int quickFind(int[] array, int aim) {
        int left = 0;
        int index = 0;
        int right = array.length - 1;
        while (true) {
            index = quickSort(array, left, right);
            if (aim < index) {
                right = index - 1;
            } else if (aim > index) {
                left = index + 1;
            } else {
                break;
            }
        }
        return array[index];
    }

    public static int quickSort(int[] array, int left, int right) {
        int initRight = right;
        int aim = array[initRight];
        right--;
        while (true) {
            while (array[left] < aim && left < initRight) {
                left++;
            }
            while (array[right] > aim && right > 0) {
                right--;
            }
            if (left >= right) {
                break;
            } else {
                swap(array, left, right);
            }
        }
        swap(array, left, initRight);
        return left;
    }

    public static void swap(int[] array, int leftIndex, int rightIndex) {
        int temp = array[leftIndex];
        array[leftIndex] = array[rightIndex];
        array[rightIndex] = temp;
    }

    // 冒泡排序
    public static void bubbleSort(int[] array) {
        // 每次循环，都能冒泡出剩余元素中最大的元素，因此需要循环 array.length 次
        for (int i = 0; i < array.length; i++) {
            // 每次遍历，只需要遍历 0 到 array.length - i - 1中元素，因此之后的元素都已经是最大的了
            for (int j = 0; j < array.length - i - 1; j++) {
                // 交换元素
                if (array[j] > array[j + 1]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }

    // 选择排序
    public static void selectSort(int[] array) {
        //最大值的下标
        int maxIndex;
        //第一层循环,从数组尾部开始,逐一取值
        for (int i = array.length - 1; i >= 0; i--) {
            maxIndex = i;
            //选择出最大值的下标
            for (int j = 0; j < i; j++) {
                if (array[j] > array[maxIndex]) {
                    maxIndex = j;
                }
            }
            //交换
            swap(array, maxIndex, i);
        }
    }

    // 插入排序
    public static void insertSort(int[] array) {
        //需要插入的目标值
        int aim;
        //从倒数第二个开始,遍历n-1次
        for (int i = array.length - 2; i >= 0; i--) {
            //赋值为第i个,第一次赋值为倒数第二个
            aim = array[i];
            //从选中的值的后面来确定插入的位置
            for (int j = i + 1; j < array.length; j++) {
                //目标值大于当前循环的值,把当前循环的值赋值给前一位
                if (array[j] < aim) {
                    array[j - 1] = array[j];
                }
                //目标值小于的时候,把aim赋值给当前值的前一位(与上面判断中的代码不会在同一次内循环中执行)
                if (array[j] > aim) {
                    array[j - 1] = aim;
                    break;
                }
                //特殊情况判断,如果到了数组尾部,直接将aim赋值给当前位置
                if (j == array.length - 1) {
                    array[j] = aim;
                    break;
                }
            }
        }
    }

    // 归并排序，返回排好序的数组
    public static int[] mergeSort(int[] array) {
        //递归截止的条件
        if (array.length == 1) {
            return array;
        }
        //将数组分成左右两部分
        int[] left = subArray(array, 0, (array.length) / 2);
        int[] right = subArray(array, (array.length) / 2, array.length);
        //因为右边数组不会比左边的数组的长度长,因此当右边长度等于0的时候直接返回(防止后面报错)
        if (right.length == 0) {
            return array;
        }
        //递归执行获取排序后的数组
        int[] leftSort = mergeSort(left);
        int[] rightSort = mergeSort(right);
        //i表示左边数组的下标
        int i = 0;
        //j表示右边数组的下标
        int j = 0;
        //对给定的数组排序
        for (int k = 0; k < array.length; k++) {
            //当左边遍历为之后,可以直接把当前右边部分的值赋值给当前数组的位置
            if (i == left.length) {
                array[k] = rightSort[j];
                //j的下标+1
                j++;
                //跳出本次循环
                continue;
            }
            //同上
            if (j == rightSort.length) {
                array[k] = leftSort[i];
                i++;
                continue;
            }
            //如果左边部分比右边的小
            if (leftSort[i] < rightSort[j]) {
                //当前左边位置的值赋值给当前位置
                array[k] = leftSort[i];
                i++;
            } else {
                //相反
                array[k] = rightSort[j];
                j++;
            }
        }
        //返回排序之后的数组
        return array;
    }

    // 拷贝原数组的部分内容，从 left 到 right
    public static int[] subArray(int[] source, int left, int right) {
        // 创建一个新数组
        int[] result = new int[right - left];
        // 依次赋值进去
        for (int i = left; i < right; i++) {
            result[i - left] = source[i];
        }
        return result;
    }

    // 快速排序
    public static void quickSort(int[] array) {
        // 调用快速排序的核心，传入left，right
        quickSortCore(array, 0, array.length - 1);
    }

    // 快速排序的核心，同样也是递归函数
    public static void quickSortCore(int[] array, int left, int right) {
        // 递归基准条件，left >= right 即表示数组只有1个或者0个元素。
        if (left >= right) {
            return;
        }
        // 根据轴分区
        int pivotIndex = partition(array, left, right);

        // 递归调用左侧和右侧数组分区
        quickSortCore(array, left, pivotIndex - 1);
        quickSortCore(array, pivotIndex + 1, right);
    }

    // 对数组进行分区，并返回当前轴所在的位置
    public static int partition(int[] array, int left, int right) {
        int pivot = array[right];

        int leftIndex = left;
        int rightIndex = right - 1;
        while (true) {
            // 左指针移动
            while (array[leftIndex] <= pivot && leftIndex < right) {
                leftIndex++;
            }
            // 右指针移动
            while (array[rightIndex] >= pivot && rightIndex > 0) {
                rightIndex--;
            }

            if (leftIndex >= rightIndex) {
                break;
            } else {
                swap(array, leftIndex, rightIndex);
            }
        }

        swap(array, leftIndex, right);
        return leftIndex;
    }

    public static void main(String[] args) {
//        int[] array = {72, 77, 48, 17, 71, 2, 25, 97, 82, 5, 2, 18, 15, 57, 7, 48, 93, 47, 38, 74, 18, 93, 98, 41, 54, 4, 47, 4, 63, 76};
        int[] array = {1, 3, 9};
        // Arrays.toString 可以方便打印数组内容
        System.out.println(Arrays.toString(array));
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
